Lab 7: Antrian Prioritas & Heap

Apa yang Kita Bangun 🎯

  • Struktur Data: Sebuah Antrian Prioritas (PQ).
    • Ini adalah tipe data abstrak seperti daftar atau antrian, tetapi dengan sentuhan khusus.
    • Setiap item memiliki "prioritas" (kunci).
    • Ketika Anda "mengeluarkan," Anda selalumendapatkan item dengan prioritas tertinggi.
  • Operasi:
    • 1. push(k)
    • 2. peek()
    • 3. pop()
  • Implementasi:Kita akan menggunakan Heap Maksimum Biner.
  • Mengapa Heap? Ini efisien! Heap memberi kita:
    • push: O(log N)
    • pop: O(log N)
    • peek: O(1)

Apa itu Heap Maksimum?

Pohon biner dengan dua aturan sederhana:

1. Properti Bentuk

Ini adalah pohon biner lengkap. Semua tingkat terisi penuh, kecuali *mungkin* tingkat terakhir, yang diisi dari kiri ke kanan. Tidak ada celah.

Klik daun untuk menghapus

2. Properti Heap Maksimum

Kunci orang tua adalah lebih besar dari atau sama dengankunci anak-anaknya. Ini menjamin bahwa elemen yang terbesarselalu berada di akar.

Menyimpan Pohon 💾

Karena pohonnya lengkap, kita bisa menyimpannya sempurna dalam sebuah array sederhana.

Matematika Indeks (berbasis 0)

Untuk simpul pada indeks i:

  • Orang Tua(i - 1) // 2
  • Anak Kiri2 * i + 1
  • Anak Kanan2 * i + 2

Panduan:Hafalkan rumus-rumus ini! Mereka adalah kunci untuk menavigasi "pohon" di dalam array Anda.